In networks such as enterprise, Metro-Area, and Wide-Area networks, most of the network topologies consist of meshes and rings. These networks are expected to support a quality of service (QoS), pursuant to Service Level Agreements (SLAs) between the customers and the service provider, required to support voice, video, and data applications.
Traditional networks, such as ATM, use “per flow” management. A flow is a TCP/UDP connection that is uniquely defined by the following fields: IP source address, IP destination address, protocol number (TCP/UDP), TCP/UDP source port number, and destination port number. Each flow consists of one or more packets requiring the same connection. Each flow is managed by queuing the packets in the flow and scheduling the transmission of the flow through the network. The flows are given various priority levels depending upon the customer's Service Level Agreements, which determine whether the flows are delayed or dropped when there is congestion in the network or within the source node itself. This per flow management provides end-to-end bandwidth guarantees while maintaining per flow shaping and leads to minimum de-jittering delay at the end receiver. Network flows are extremely short lived (60% are less than five packets long) and extremely dynamic in nature.
In high-end routers, which process as many as fifty million packets per second, it is very costly (in terms of processing time) to separately schedule millions of flows that traverse through the backbone nodes. Further, maintaining millions of queues and scheduling each queue according to a fair queuing mechanism is very expensive. And, using the protocol layer to process per flow signaling messages is computationally very expensive.
To increase the effective length of a flow, the flows may be aggregated by customer, node, Multiple Protocol Label Switching (MPLS) label, or any other aggregate. An aggregation of flows is typically designated by a common ID or label in the packets' headers, depending on what type of flows are to be aggregated, such as flows by a single customer or a single node. This reduces the number of queues somewhat but still would result in a router needing to support queuing and scheduling of millions of queues.
In contrast to per flow queuing and scheduling, class based queuing networks have emerged. A class is basically a level of priority of a packet. Such class based queuing is advantageous because of its scalability and seamless integration with IP network protocols. Class based models scale well because the number of classes supported (typically eight) remains constant while the link rate increases. The class of a packet is designated in a field in the IP header of a package. The flows are aggregated according to their class and are queued and scheduled according to the class.
The highest class is for voice traffic (and other high priority traffic) whose packets cannot be delayed or delivered out of sequence. The lowest class is best-effort service. Other classes include various levels of delay insensitive services having committed bandwidth allocations and over-committed bandwidth allocations. The customers subscribe to particular classes and bandwidths, where the higher classes and bandwidths are more expensive.
When the network becomes congested, packets within classes that guarantee a particular bandwidth to the customers do not get dropped. The packets in the lower classes (e.g., over-committed classes) are dropped in accordance with various algorithms due to the congestion.
Multiple customers may share the same class queue in a router. Some customers sharing a class queue have Service Level Agreements with the service provider that provide for a bandwidth allocation that is greater than the bandwidth allocation provided for other customers sharing the class. In such cases, bandwidth degradation is controlled by dropping packets in accordance with various algorithms. However, in the prior art, the dropping of packets in a certain class due to congestion is not dependent on the particular customer associated with the packets. Therefore, although a certain customer has paid for a higher bandwidth, that customer's packets are just as likely to be dropped by the shared class queue as packets for a customer that has paid for less bandwidth. This is an unfair situation to the customer who has paid for a larger bandwidth.
What is needed is a more fair technique to drop packets in class based queuing.